/*
 * @lc app=leetcode id=264 lang=cpp
 *
 * [264] Ugly Number II
 */
class Solution {
public:
    int nthUglyNumber(int n) {

        if (n < 1) {
            return 0;
        }

        vector<int> memo(n+1);
        memo[1] = 1;

        int k2 = 1;
        int k3 = 1;
        int k5 = 1;

        int i = 2;
        while (i <= n) {

            memo[i] = std::min(std::min(memo[k2]*2, memo[k3]*3), memo[k5]*5);

            if (memo[i] == memo[k2]*2) {
                k2++;
            } 
            
            if (memo[i] == memo[k3]*3) {
                k3++;
            } 
            
            if (memo[i] == memo[k5]*5) {
                k5++;
            }

            i++;
        }
        return memo[n];
    }
};

